#include <iostream>
#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> validStrings(int n) {
        if (n == 1) return { "0", "1" };

        std::vector<std::string> ans;
        std::vector<std::string> prev = validStrings(n - 1);

        for (const std::string& s : prev) {
            if (s[0] == '1') ans.push_back('0' + s);
            ans.push_back('1' + s);
        }

        return ans;
    }
};

int maints() {
    Solution sol;
    int n = 3;
    std::vector<std::string> result = sol.validStrings(n);

    for (const std::string& s : result) {
        std::cout << s << std::endl;
    }

    return 0;
}